import pandas as pd

def hungarian_algorithm(cost_matrix):
    n = len(cost_matrix)
    u = [0] * n
    v = [0] * n
    p = [-1] * n
    z = [False] * n  # 标记0元素
    transformations = 0  # 记录矩阵变换次数

    # 1. 从每一行减去行中的最小值
    for i in range(n):
        min_val = min(cost_matrix[i])
        for j in range(n):
            cost_matrix[i][j] -= min_val
        u[i] += min_val

    # 2. 从每一列减去列中的最小值
    for j in range(n):
        min_val = min(cost_matrix[k][j] for k in range(n))
        for i in range(n):
            cost_matrix[i][j] -= min_val
        v[j] += min_val

    # 3. 覆盖所有零元素
    while True:
        covered_rows = [False] * n
        covered_cols = [False] * n
        for i in range(n):
            for j in range(n):
                if cost_matrix[i][j] == 0 and not covered_rows[i] and not covered_cols[j]:
                    covered_rows[i] = True
                    covered_cols[j] = True
                    z[j] = True
                    break
        if all(z):
            break
        else:
            # 3.1 找到最小的非零元素
            min_val = float('inf')
            for i in range(n):
                if not covered_rows[i]:
                    for j in range(n):
                        if not covered_cols[j] and cost_matrix[i][j] > 0:
                            min_val = min(min_val, cost_matrix[i][j])
            # 3.2 更新成本矩阵
            for i in range(n):
                if not covered_rows[i]:
                    for j in range(n):
                        if not covered_cols[j] and cost_matrix[i][j] > 0:
                            cost_matrix[i][j] -= min_val
            for j in range(n):
                if not covered_cols[j]:
                    v[j] += min_val
            transformations += 1  # 增加变换次数

    # 4. 分配任务
    for i in range(n):
        for j in range(n):
            if cost_matrix[i][j] == 0 and z[j]:
                p[i] = j
                z[j] = False
                break

    return p, transformations

# 读取Excel文件
file_path = "C:\\Users\\86191\\Desktop\\资料PPT\\大三学期\\智能优化算法\\指派问题矩阵.xlsx"  # 替换为你的文件路径
df = pd.read_excel(file_path, index_col=0)

# 将DataFrame转换为成本矩阵
cost_matrix = df.values.tolist()

# 应用匈牙利算法
assignment, transformations = hungarian_algorithm(cost_matrix)

# 输出结果
workers = df.index.tolist()
tasks = df.columns.tolist()
print("最优指派结果:")
for i, task in enumerate(assignment):
    print(f"{workers[i]} -> {tasks[task]}")
#print(f"矩阵变换次数: {transformations}")

